package BinaryTreeExer;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-20
 * Time: 11:47
 */

/**
 *  另一棵树的子树:
 * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
 *
 * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [3,4,5,1,2], subRoot = [4,1,2]
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
 * 输出：false
 */

/**
 如果设q 有n个节点，p有m个节点
 时间复杂度为 0(n * m)
 */
public class BinaryTreeExercise2 {

    static class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
       }
   }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {

        //这里是递归遍历root的返回条件，不能省略，我们要在root这颗大树上遍历找subRoot树
        if(root == null) {
            return false;
        }

        //判断整个树的根只有一次，就用isSameTree
        if(isSameTree(subRoot, root)) return true;
        //来到第二层，这里要递归遍历root，
        //因为这棵树可能包含subRoot的子树

        if(isSubtree(root.left,subRoot)) return true;//root的左树
        if(isSubtree(root.right,subRoot)) return true;//root的右树

        return false;

    }

    //判断两棵树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //先判断结构是否一样
        if(p != null && q == null || q != null && p == null) {
            return false;
        }
        //走到这里，两个都为空或者两个都不为空

        //排除都为空树，但是空树也是树
        if(p == null && q == null) {
            return true;
        }
        //走到这里两个都不为空

        //开始判断树，根的值是否一样
        if(p.val != q.val) {
            return false;
        }

        //树都不为空，树根的值一样就判断：左子树 && 右边是否一样

        if(isSameTree(p.left, q.left)
                && isSameTree(p.right, q.right)) {
            return true;
        }

        return false;
    }
}
